package com.zp.self.module.level_4_算法练习.算法.贪心;

import java.util.Stack;

/**
 * @author By ZengPeng
 */
public class 力扣_45_跳跃游戏II {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_45_跳跃游戏II().jump(new int[]{2,3,1,1,4}));
        System.out.println(new 力扣_45_跳跃游戏II().jump(new int[]{2,3,0,1,4}));
        System.out.println(new 力扣_45_跳跃游戏II().jump(new int[]{2}));
        System.out.println(new 力扣_45_跳跃游戏II().jump(new int[]{1}));
        System.out.println(new 力扣_45_跳跃游戏II().jump(new int[]{0}));
        System.out.println(new 力扣_45_跳跃游戏II().jump(new int[]{8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,6,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5}));

        System.out.println(new 力扣_45_跳跃游戏II().jump(new int[]{1,2,1,1,1}));
    }

    /**
    题目：给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
     数组中的每个元素代表你在该位置可以跳跃的最大长度。
     你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     假设你总是可以到达数组的最后一个位置。
      
     示例 1:
     输入: nums = [2,3,1,1,4]
     输出: 2
     解释: 跳到最后一个位置的最小跳跃数是 2。
          从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

     示例 2:
     输入: nums = [2,3,0,1,4]
     输出: 2

    分析：【P 💗💗💗】 解题超时
       1.回溯：【超时了】判断当前值的大小,总是从最大值开始，不断减少目标值。
                当目标值为0时跳出返回当前的长度 ，不行的话就-1
            剪枝:我当前值已经够跨越到长度了，就完成了呀
        2.贪心算法：找到当前范围内，i+nums[i]的最大值
           --执行用时：1 ms, 在所有 Java 提交中击败了99.12%的用户

    边界值 & 注意点：
       1.如果落脚点下标值为0 则不能跳
        2.[0] 直接0
     3.超时了;[8,2,4,4,4,9,5,2,5,8,8,0,8,6,9,1,1,6,3,5,1,2,6,6,0,4,8,6,0,3,2,8,7,6,5,1,7,0,3,4,8,3,5,9,0,4,0,1,0,5,9,2,0,7,0,2,1,0,8,2,5,1,2,3,9,7,4,7,0,0,1,8,5,6,7,5,1,9,9,3,5,0,7,5]
     **/
    public int jump(int[] nums) {
        if(nums.length==1)return 0;
        int jump=0,start=0,max=start;
        while (start<nums.length-1 &&  start+nums[start]<nums.length-1){
            int end = Math.min(nums.length-1,start+nums[start]);
            for (int i = start+1; i <=end; i++) {
                if(i+nums[i]>max+nums[max])
                    max=i;
            }
            start=max;jump++;
        }
        return ++jump;
    }

    // 1.回溯：【超时了】判断当前值的大小,总是从最大值开始，不断减少目标值。
    private int recursive(int[] nums, int i, Stack<Integer> stack, int min) {
        if(i+nums[i]+1>=nums.length) {
            min = Math.min(min,stack.size());
            return min;
        }
        if(stack.size()==min)return min;//剪枝,后续的长度肯定大于了
        for (int j = i+nums[i]; j > i && j <nums.length; j--) {//这里要找最大值啊
            if(nums[j]==0)continue;
            stack.push(nums[j]);
            min = recursive(nums, j, stack, min);
            stack.pop();
        }
        return min;
    }
}
